package com.wengu.recursion;

import org.junit.jupiter.api.Test;

/**
 * 八皇后问题
 * @author whl
 * @Description
 * @date 2021/7/1 10:49
 * @Version 1.0
 */
public class EightQueens {
    int max = 8;
    // 定义一维数组，索引n表示第n+1个皇后，同时表示第n+1行，arr[n]的值表示第arr[n]+1列，
    int[] arr = new int[max];
    // 定义解法个数
    int count ;

    @Test
    public void test(){
        place(0);
    }

    /**
     * 放置第n+1个皇后
     * @param n
     */
    public void place(int n){

        if (n == max){
            // 此时已排列好8个皇后
            // 打印排列顺序
            print();
            return ;
        }
        // 依次入围皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            // 放置第(n+1)个皇后，如果放到0的位置arr[n]=i，
            arr[n] = i;
            // 不冲突则放下一个皇后，
            if (check(n)){
                place(n + 1);
            }
            // 如果冲突则放置到下一个位置，执行arr[n]=i
        }

    }

    /**
     * 校验第n+1个皇后放置的位置
     * @param n 第n+1个皇后
     * @return
     */
    public boolean check(int n){
        for (int j = 0; j < n; j++) {
            // 判定是否在同一列或者在同一斜线上，如果是则不能放置。
            if (arr[j] == arr[n] || Math.abs(arr[j]-arr[n]) == Math.abs(j-n)){
                return false;
            }
            // 因每次n都是递增的，所以不存在两个皇后再同一行的情况，则不需要去判断是否在同一行上
        }
        return true;
    }

    public void print(){
        count++;
        System.out.print("八皇后问题第" + count + "种解法：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print((arr[i] + 1) + " ");
        }
        System.out.println();
    }

}
